class Solution {
    public:
        int _n;
        int ret = 0;
        int is_existent[16]= {0};
        int countArrangement(int n) {
            _n = n;
            dfs(1);
            return ret;
        }
        void dfs(int pos){
            if(pos == _n+1){
                ret++;
                return;
            }
            for(int i = 1 ; i <= _n ; i++){
                if(is_existent[i] == 0){
                    if(i % pos == 0 || pos%i == 0){
                        is_existent[i] =1;
                        dfs(pos+1);
                        is_existent[i] = 0;
                    }else{
                        // 不满足条件时，继续尝试下一个i，无需return
                    }
                }
            }
        }
    };